class Solution {
public:
    int ret = 0;
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    int dfs(vector<vector<int>>& s,int x,int y,vector<vector<int> >& dp){
        if(dp[x][y] != 0){
            return dp[x][y];
        }
        for(int i = 0;i < 4;i++){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
           
            if(xx >= 0 && xx < s.size() && yy >= 0 && yy < s[0].size() && s[xx][yy] > s[x][y]){
                dp[x][y] = max(dfs(s,xx,yy,dp)+1,dp[x][y]);
                ret = max(ret,dp[x][y]);
            }
        }
        return dp[x][y];
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        vector<vector<int> > dp(matrix.size(),vector<int>(matrix[0].size(),0));
        for(int i = 0;i < matrix.size();i++){
            for(int j = 0;j < matrix[i].size();j++){
                dfs(matrix,i,j,dp);  
            }
        }
        return ret + 1;
    }
};
